/*
 * @lc app=leetcode.cn id=388 lang=cpp
 *
 * [388] 文件的最长绝对路径
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;

bool isFile(const string &path)
{
    return path.find_first_of('.') != path.npos;
}

struct Node
{
    string s;
    bool is_file; //判断是否是文件
    int len;      //记录文件夹名或者文件名的长度
    Node *parent; //父级目录

    Node() : is_file(false), len(0), parent(nullptr) {}

    Node(const string &s_, Node *parent_) : s(s_),
                                            is_file(false),
                                            len(0),
                                            parent(parent_)
    {
        is_file = isFile(s);
        len = s.length();
    }
};

class Solution
{
public:
    int lengthLongestPath(string input)
    {
        // Node* root = new Node(false, 0, nullptr);

        vector<vector<Node *>> vs;
        vs.push_back(vector<Node *>());
        vs[0].push_back(nullptr);
        vs.push_back(vector<Node *>());

        // (vs.end() - 1)->push_back(root);
        int i = 0, j = 1;
        while (j < input.size() && input[j] != '\n')
            ++j;
        (vs.end() - 1)->push_back(new Node(input.substr(i, j - i), nullptr));

        ++j;
        while (j < input.size() && input[j] == '\t')
            ++j;
        i = j;
        if (i < input.size())
        {
            input += "\n";
            for (; j < input.size(); j++)
            {
                if (input[j] == '\n')
                {
                    // 判断当前文件或者文件夹所处的level级别
                    int k = i;
                    while (input[--k] == '\t') //无需特殊保证k > 0
                        ;
                    //此时有 input[k] == '\n'
                    int level = i - k;
                    if (level == vs.size())
                    {
                        vs.push_back(vector<Node *>());
                    }
                    vs[level].push_back(new Node(input.substr(i, j - i), *(vs[level - 1].end() - 1)));

                    i = j + 1;
                    while (i < input.size() && input[i] == '\t')
                        ++i;
                    j = i;
                }
            }
        }

        //从后向前查找

        int ans = 0;

        for (int i = vs.size() - 1; i > 0; i--)
        {
            auto &v = vs[i];
            for (int j = 0; j < v.size(); j++)
            {
                if (v[j]->is_file)
                {
                    Node *p = v[j]->parent;
                    int len = v[j]->len;
                    while (p)
                    {
                        len += p->len + 1;
                        p = p->parent;
                    }
                    ans = max(ans, len);
                }
            }
        }

        return ans;
    }
};

// int main()
// {
//     string input = "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext";
//     cout << Solution().lengthLongestPath(input) << endl;
//     return 0;
// }

// @lc code=end
